package com.nanbei.graph;

import java.util.*;

/**
 * @ClassDescription: 迪克斯特拉(最短路径算法)
 * @JdkVersion: 1.8
 * @Author: libs
 * @Created: 2024/7/2 10:24
 */
public class DijkstraPriorityQueue {
    public static void main(String[] args) {
        Vertex v1 = new Vertex("v1");
        Vertex v2 = new Vertex("v2");
        Vertex v3 = new Vertex("v3");
        Vertex v4 = new Vertex("v4");
        Vertex v5 = new Vertex("v5");
        Vertex v6 = new Vertex("v6");

        v1.setEdges(Arrays.asList(new Edge(v3, 9), new Edge(v2, 7), new Edge(v6, 14)));
        v2.setEdges(Arrays.asList(new Edge(v4, 15)));
        v3.setEdges(Arrays.asList(new Edge(v4, 11), new Edge(v6, 2)));
        v4.setEdges(Arrays.asList(new Edge(v5, 6)));
        v5.setEdges(Arrays.asList());
        v6.setEdges(Arrays.asList(new Edge(v5, 9)));

        List<Vertex> graph = Arrays.asList(v1, v2, v3, v4, v5, v6);
        dijkstra(graph, v1);
    }

    /**
     * 迪克斯特拉 算法描述 (使用优先级队列)
     * 1. 将所有顶点标记为未访问。创建一个未访问顶点的集合。
     * 2. 为每个顶点分配一个临时距离值
     * - 对于我们的初始顶点，将其设置为零
     * - 对于所有其他顶点，将其设置为无穷大。
     * 3. 每次选择最小临时距离的未访问顶点，作为新的当前顶点
     * 4. 对于当前顶点，遍历其所有未访问的邻居，并更新它们的临时距离为更小
     * - 例如，1->6 的距离是 14，而1->3->6 的距离是11。这时将距离更新为 11
     * - 否则，将保留上次距离值
     * 5. 当前顶点的邻居处理完成后，把它从未访问集合中删除
     *
     * @param vertexList 所有顶点集合
     * @param v     初始顶点
     */
    private static void dijkstra(List<Vertex> vertexList, Vertex v) {
        // 默认按照 dist 进行排序
        PriorityQueue<Vertex> vertexPriorityQueue = new PriorityQueue<>(Comparator.comparingInt(value -> value.getDist()));
        v.setDist(0);
        vertexPriorityQueue.addAll(vertexList);



        while (!vertexPriorityQueue.isEmpty()){
            System.out.println(vertexPriorityQueue);
            // 每次选择最小临时距离的未访问顶点，作为新的当前顶点
            Vertex vertex = vertexPriorityQueue.peek();
            // 对于当前顶点，遍历其所有未访问的邻居，并更新它们的临时距离为更小
            updateDist(vertex,vertexPriorityQueue);
            // 前顶点的邻居处理完成后，把它从未访问集合中删除
            vertexPriorityQueue.poll();

        }

        for (Vertex vertex : vertexList) {
            System.out.println(vertex.getName()+" "+ vertex.getDist()+" "+ (vertex.getPerv() == null? "null":vertex.getPerv().getName()));
        }

    }

    private static void updateDist(Vertex vertex, PriorityQueue<Vertex> vertexPriorityQueue) {
        List<Edge> edges = vertex.getEdges();
        int dist = vertex.getDist();
        for (Edge edge : edges) {
            Vertex linked = edge.getLinked();
            if (!linked.isVisited()) {
                int weight = edge.getWeight();
                if (weight+dist < linked.getDist()){
                    vertexPriorityQueue.remove(linked);
                    linked.setDist(weight+dist);
                    linked.setPerv(vertex);
                    vertexPriorityQueue.add(linked);
                }
            }
        }
    }
}
